import java.util.ArrayList;
import java.util.List;

public class MyStack {

    private List<String> list;
    private int size;
    public String top;

    public MyStack() {
        list = new ArrayList();
        size = 0;
        top = null;
    }

    public int size() {
        return size;
    }

    public void push(String s) {
        list.add(s);
        top = s;
        size++;
    }
    public String pop() {
        String s = list.get(size - 1);
        list.remove(size - 1);
        size--;
        top = size == 0 ? null : list.get(size - 1);
        return s;
    }
}
 class reversePolish {
     private static MyStack ms1 = new MyStack();//生成逆波兰表达式的栈
     public static List<String> transform(String s) {
         s = s.replaceAll(" ", "");
         List<String> list = new ArrayList();//存储中序表达式
         int i = 0;
         char c;
         do {
             if (((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57)) {
                 list.add("" + c);
                 i++;
             } else {
                 StringBuilder stringBuilder = new StringBuilder();
                 while ((i < s.length() && ((c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57))
                         || (i < s.length() && (c = s.charAt(i)) == '.')) {
                     stringBuilder.append(c);
                     i++;
                 }
                 list.add(stringBuilder.toString());
             }
         } while (i < s.length());
         //对特殊负号进行修改
         for (int j = 0; j < list.size(); j++) {
             if(list.get(j).equals("-") && (j == 0 || (j > 0 && list.get(j - 1).equals("(")))) {
                 list.set(j, "-1");
                 list.add(j + 1, "*");
             }
         }
         return list;
     }

     /**
      * 将中缀表达式转换为逆波兰表达式
      */
     public static List<String> parse(String s) {
         List<String> listStr = transform(s);
         List<String> retList = new ArrayList<>();
         for (String ss : listStr) {
             if (ss.matches("^(-?\\d+)(\\.\\d+)?$")) {
                 retList.add(ss);
             } else if (ss.equals("(")) {
                 ms1.push(ss);
             } else if (ss.equals(")")) {
                 while (!ms1.top.equals("(")) {
                     retList.add(ms1.pop());
                 }
                 ms1.pop();
             } else {
                 while (ms1.size() != 0 && getValue(ms1.top) >= getValue(ss)) {
                     retList.add(ms1.pop());
                 }
                 ms1.push(ss);
             }
         }
         while (ms1.size() != 0) {
             retList.add(ms1.pop());
         }
         return retList;
     }

     /**
      * 获取运算符优先级
      * <p>
      * +,-为1 *,/,^,%为2 ()为0
      */

     public static int getValue(String s) {
         if (s.equals("+")) {
             return 1;
         } else if (s.equals("-")) {
             return 1;
         } else if (s.equals("*")) {
             return 2;
         } else if (s.equals("/")) {
             return 2;
         } else if (s.equals("^")) {
             return 2;
         } else if (s.equals("%")) {
             return 2;
         } else {
             return 0;
         }
     }
 }